import copy
from typing import List


# 216. 组合总和 III
# 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
# 只使用数字1到9
# 每个数字最多使用一次
# 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
# 2 <= k <= 9
# 1 <= n <= 60
def combinationSum3(k: int, n: int) -> List[List[int]]:
    re = list()

    nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    def back_track(target: int, count: int,
                    current_index: int, current_list: List[int],
                    result_list: List[List[int]]):
        # 刚好找到了
        if count == 0 and target == 0:
            copy_current_list = copy.deepcopy(current_list)
            result_list.append(copy_current_list)
            return

        # target < 0：由于是排序好的数，无法找到
        # count < 0：用尽了 count 次数，无法找到
        if target < 0 or count < 0:
            return

        for start_index in range(current_index, len(nums)):
            num = nums[start_index]
            # 后面需要回溯这些
            target -= num
            count -= 1
            current_list.append(num)
            # 递归执行
            back_track(target, count, start_index + 1, current_list, result_list)
            # 回溯
            current_list.pop()
            count += 1
            target += num

    back_track(n, k, 0, [], re)

    return re


result = combinationSum3(3, 7)
print(f"result:{result}")

result = combinationSum3(3, 9)
print(f"result:{result}")

result = combinationSum3(4, 1)
print(f"result:{result}")

result = combinationSum3(9, 50)
print(f"result:{result}")

result = combinationSum3(2, 10)
print(f"result:{result}")
